package com.study.yangfei.mystudy.activity;

import android.os.Bundle;
import android.support.design.widget.FloatingActionButton;
import android.support.design.widget.Snackbar;
import android.support.v7.app.AppCompatActivity;
import android.support.v7.widget.Toolbar;
import android.util.Log;
import android.view.View;

import com.study.yangfei.mystudy.R;

import java.util.ArrayList;
import java.util.List;

public class AlogQuickSortActivity extends AppCompatActivity {

    ArrayList<sortObj> unSort = new ArrayList<sortObj>();
    ArrayList<sortObj> sorted = new ArrayList<sortObj>();

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_alog_quick_sort);
        Toolbar toolbar = (Toolbar) findViewById(R.id.toolbar);
        setSupportActionBar(toolbar);

        unSort.add(new sortObj(12));
        unSort.add(new sortObj(3));
        unSort.add(new sortObj(2));
        unSort.add(new sortObj(11));
        unSort.add(new sortObj(2));
        unSort.add(new sortObj(89));
        unSort.add(new sortObj(111));
        unSort.add(new sortObj(1));


        sorted = quickSort(unSort);


        Log.e("quickSort","---------------unSort-----------------------");
        for(sortObj bo:unSort){
            Log.e("quickSort","unS object value = " + bo.value);
        }

        Log.e("quickSort","---------------sorted-----------------------");
        for(sortObj bo:sorted){
            Log.e("quickSort","s object value = " + bo.value);
        }
    }

    class sortObj{
        public int key;
        public int value;
        public sortObj(int v){
            value = v;
        }
    }



    public ArrayList<sortObj> quickSort(List<sortObj> unS){
        ArrayList<sortObj> s = new ArrayList<sortObj>();
        Log.e("quickSort","---------------unS-----------------------");
        for(sortObj bo:unS){
            Log.e("quickSort","unS object value = " + bo.value);
        }

        if(unS.size() == 1){
            s.add(unS.get(0));
        }

        if(unS.size() == 2){
            if(unS.get(0).value < unS.get(1).value){
                s.add(unS.get(0));
                s.add(unS.get(1));
            }else{
                s.add(unS.get(1));
                s.add(unS.get(0));
            }
        }

        if(unS.size()>2){
            int halfSize = unS.size()/2;
            ArrayList<sortObj> sLeft = quickSort(unS.subList(0,halfSize));
            ArrayList<sortObj> sRight = quickSort(unS.subList(halfSize,unS.size()));
            s = mergeArray(sLeft,sRight);
        }

        Log.e("quickSort","---------------s-----------------------");
        for(sortObj bo:s){
            Log.e("quickSort","s object value = " + bo.value);
        }
        return s;
    }

    public ArrayList<sortObj> mergeArray(ArrayList<sortObj> aList,ArrayList<sortObj> bList){
        ArrayList<sortObj> resultArr = new ArrayList<>();

        int indexA = 0;
        int indexB = 0;
        for(int index = 0;index<bList.size() + aList.size();index++){
            sortObj minorObj;

            sortObj objA;
            sortObj objB;

            if(indexA < aList.size()){
                objA= aList.get(indexA);
            }else{
                objA=new sortObj(0);
            }

            if(indexB < bList.size()){
                objB= bList.get(indexB);
            }else{
                objB=new sortObj(0);
            }


            if(objA.value < objB.value){
                minorObj = objA;
                indexA++;
            }else{
                minorObj = objB;
                indexB++;
            }

            if(indexA > aList.size()){
                minorObj = objB;
                indexB++;
            }

            if(indexB > bList.size()){
                minorObj = objA;
                indexA++;
            }

            resultArr.add(minorObj);
        }

        return resultArr;
    }

}
